package org.example.ch04;

import org.example.ch04.tree.ConstructTree;
import org.example.ch04.tree.TreeNode;
import org.omg.CORBA.MARSHAL;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
 * 给定一个二叉树，找出其最大深度。
 *
 * 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
 *
 * 说明: 叶子节点是指没有子节点的节点。
 */
public class MaxDepth {

    public static void main(String[] args) {
        //创建一个二叉树
        TreeNode treeNode = ConstructTree.constructTree(new Integer[]{3,9,20,null,null,15,7});
//        int result = maxDepth(treeNode);
//        int result = solution1(treeNode,0,0);
        int result = solution2(treeNode);
        System.out.println(result);
    }

    public  static  int maxDepth(TreeNode root) {
        //递归的终结条件
        if(root==null){
            return 0;
        }

        int leftNum =maxDepth(root.left);
        //执行本层逻辑 下探到下一层递归，传入主角
        int rightNum =maxDepth(root.right);

        int result = Math.max(leftNum,rightNum)+1;

        //清理本层
        return result;
    }

    public static int solution1(TreeNode root,int leftNum,int rightNum){
        //递归的终结条件
        if(root==null){
            return 0;
        }

        solution1(root.left,leftNum+1,rightNum);
        //执行本层逻辑 下探到下一层递归，传入主角
        solution1(root.right,leftNum,rightNum+1);

        int result = Math.max(leftNum,rightNum)+1;

        //清理本层
        return result;
    }


    public static int solution2(TreeNode root){
       if(root==null){
           return 0;
       }
        Deque<TreeNode> queue = new LinkedList<TreeNode>();
        int ans=0;
        queue.offer(root);
        while (!queue.isEmpty()){
            int size = queue.size();
            while (size>0){
               TreeNode node = queue.poll();
               if(node.left!=null){
                    queue.offer(node.left);
               }
               if(node.right!=null){
                    queue.offer(node.right);
               }
                size--;
            }
            ans++;
        }
        return ans;
    }
}
